package sol.problems;

import def.ListNode;

import java.util.HashMap;

/**
 * Created by lkk on 2016/8/18.
 */
public class LinkedListCopy {

    public static Node copy(Node head) {
        //如果链表为空，则直接返回
        if (head == null)
            return null;

        HashMap<Node, Node> map = new HashMap<Node, Node>();//用于存储原链表与副本之间结点的对应关系
        Node copyHead = new Node(head.value);//副本链表
        map.put(head, copyHead);
        Node ptr = head.next;
        Node newPtr = copyHead;
        //第一次遍历，不复制foo指针
        while (ptr != null) {
            Node newnode = new Node(ptr.value);
            map.put(ptr, newnode);
            newPtr.next = newnode;

            ptr = ptr.next;
            newPtr = newPtr.next;
        }

        //第二次遍历，修改副本链表中的foo指针
        ptr = head;
        newPtr = copyHead;
        while (ptr != null) {
            newPtr.foo = map.get(ptr.foo);
            ptr = ptr.next;
            newPtr = newPtr.next;
        }

        return copyHead;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node1.foo = node2;
        node2.foo = node4;
        node3.foo = node1;
        node4.foo = node3;

        System.out.println("原链表=================>");
        print(node1);

        Node copy = copy(node1);
        System.out.println("副本链表===============>");
        print(copy);

    }

    //打印函数，用于检验是否复制是否准确
    public static void print(Node head) {
        Node ptr = head;
        while (ptr != null) {
            System.out.println("value=" + ptr.value + ";foo.value=" + ptr.foo.value);
            ptr = ptr.next;
        }
    }
}

class Node {
    int value;
    Node next;
    Node foo;

    Node(int value) {
        this.value = value;
    }
}
